318D - Ants - CodeForces Solution

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <cassert>

using namespace std;


const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int max_side = 100;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t; cin >> n >> t;

    vector<vector<int>> g(2 * max_side + 1, vector<int>(2 * max_side + 1, 0));
    int C = 2 * max_side + 1;
    g[max_side][max_side] = n;

    queue<int> q; // pos -> num;
    if(n >= 4) q.push(max_side * C + max_side);
    while(!q.empty()){
        int cx = q.front() / C, cy = q.front() % C;
        q.pop();

        if(g[cx][cy] < 4) continue;

        g[cx][cy] -= 4;
        if(g[cx][cy] >= 4) q.push(cx * C + cy);

        for(int d = 0; d < 4; d ++){
            int nx = cx + dirs[d][0], ny = cy + dirs[d][1], npos = nx * C + ny;
            assert(0 <= nx && nx < g.size() && 0 <= ny && ny < g.size());
            g[nx][ny] += 1;
            if(g[nx][ny] >= 4) q.push(npos);
        }
    }

    while(t --){
        int x, y; cin >> x >> y;
        x += max_side, y += max_side;
        if(x < 0 || x >= g.size() || y < 0 || y >= g.size()) cout << 0 << '\n';
        else cout << g[x][y] << '\n';
    }

    return 0;
}